/*
 * region_search.cpp
 *
 *  Created on: 03.02.2013
 *      Author: Maksim Lazeba
 */

#include "region_search.h"
#include <algorithm>

typedef std::vector<point_t> points_t;
typedef region_tree::tree_node tree_node;
typedef region_tree::list_node list_node;

bool point_t::smaller(const point_t &b, int dim) const
{
	if (dim == 0)
		return x < b.x;
	else
		return y < b.y;
}
int point_t::cmp(double d, int dim) const
{
	double p;
	if (dim == 0)
		p = x;
	else
		p = y;

	if (p == d)
		return 0;
	return p < d ? -1 : 1;
}

bool point_t::between(const point_t &a, const point_t &b, int dim) const
{
	if (dim == X_DIM)
		return x >= a.x && x <= b.x;
	else
		return y >= a.y && y <= b.y;
}

bool list_node::operator<(const point_t &b) const
{
	return this->end ? false : point.smaller(b, Y_DIM);
}

bool list_node::operator<=(const point_t &b) const
{
	return this->end ? false : !b.smaller(point, Y_DIM);
}

bool list_node::operator<(const list_node &b) const
{
	if (end)
		return false;
	if (b.end)
		return true;
	return point.smaller(b.point, Y_DIM);
}

tree_node::tree_node(const point_t &p) :
		left(NULL), right(NULL), leaf(true)
{
	lb = p.x;
	rb = p.x;
	list.push_back(list_node(p, 0, 0, 0, 0, list.size()));
	list.push_back(list_node(0, 0, list.size()));
}

tree_node::tree_node(tree_node *left, tree_node *right) :
		left(left), right(right), leaf(false), lb(left->lb), rb(right->rb)
{
	typedef std::vector<list_node> list_t;
	size_t l_end = left->list.size() - 1;
	size_t r_end = right->list.size() - 1;
	list_t &l_list = left->list;
	list_t &r_list = right->list;
	size_t l_cur = 0;
	size_t r_cur = 0;
	point_t *min;
	size_t llb = 0;
	size_t lub = 0;
	size_t rlb = 0;
	size_t rub = 0;
	while (true)
	{
		min = NULL;
		if (l_cur < l_end)
			if (r_cur < r_end)
				if (l_list[l_cur] < r_list[r_cur])
					min = &(l_list[l_cur++].point);
				else
					min = &(r_list[r_cur++].point);
			else
				min = &(l_list[l_cur++].point);
		else if (r_cur < r_end)
			min = &(r_list[r_cur++].point);

		if (min == NULL)
			break;

		while (l_list[llb] < *min)
			llb++;
		while (l_list[lub] < *min)
			lub++;
		while (r_list[rlb] < *min)
			rlb++;
		while (r_list[rub] < *min)
			rub++;

		list.push_back(list_node(*min, llb, lub, rlb, rub, list.size()));
	}
	list.push_back(list_node(l_end, r_end, list.size()));
}

region_tree::tree_node* build_tree(points_t &points, int l, int r)
{
	if (r - l == 0)
		return NULL;
	if (r - l == 1)
		return new tree_node(points[l]);
	int m = (l + r) / 2;

	tree_node *left = build_tree(points, l, m);
	tree_node *right = build_tree(points, m, r);

	return new tree_node(left, right);
}

bool compareByX(const point_t &a, const point_t &b)
{
	return a.smaller(b, X_DIM);
}

region_tree::region_tree(points_t &points)
{
	std::sort(points.begin(), points.end(), compareByX);
	root = build_tree(points, 0, points.size());
}

region_tree::~region_tree()
{
	delete root;
}

tree_node::~tree_node()
{
	delete left;
	delete right;
}

void region_tree::add_from_region(const tree_node *node, const rect_t &rect,
		size_t lb_cur, size_t ub_cur, std::vector<point_t>& ans) const
{
	if (rect.lb.cmp(node->rb, X_DIM) == 1 || rect.rt.cmp(node->lb, X_DIM) == -1)
		return;
	if (ub_cur - lb_cur == 0)
		return;
	if (rect.lb.cmp(node->lb, X_DIM) < 1 && rect.rt.cmp(node->rb, X_DIM) > -1)
	{
		for (size_t i = lb_cur; i < ub_cur; i++)
			ans.push_back(node->list[i].point);
		return;
	}
	if (node->leaf)
		return;
	typedef std::vector<list_node> list_t;
	const list_t &l = node->list;
	add_from_region(node->left, rect, l[lb_cur].left_lb, l[ub_cur].left_ub,
			ans);
	add_from_region(node->right, rect, l[lb_cur].right_lb, l[ub_cur].right_ub,
			ans);
}

std::vector<point_t> region_tree::get_points_in_rect(const rect_t &rect) const
{
	points_t ans;
	auto lb = std::lower_bound(root->list.begin(), root->list.end() - 1,
			list_node(rect.lb));
	auto ub = std::upper_bound(root->list.begin(), root->list.end() - 1,
			list_node(rect.rt));
	add_from_region(root, rect, lb->position, ub->position, ans);
	return ans;
}
